1. Field of the Invention
The present invention relates to the technical field of decoders and, more particularly, to a device and method for block code error correction.
2. Description of Related Art
While data is transferring and storing in a DVD system, it is easily damaged by external factors such as scrape or dirty fingerprint on a DVD, access of an equipment misalignment and the like. Many coding techniques have been developed to reduce the possibility of data error. Error Correction Code (ECC) is a generic term for error coding correction, which adds extra redundancy information to original data to form codeword for being written into a storage media subsequently. When reading the codeword stored in the storage media, the most important thing is to convert the codeword back to the original data. Due to the extra redundancy information in the codeword, the reading equipment can understand the original data better and thus obtain higher reliable data after special decoding procedure is performed. It is definite that more redundancy can provide more information to the reading equipment and thus achieve a higher decoding performance. However, this has to sacrifice transmission rate of the data.
The development object of ECC has an important issue on system implementation for a low complicated decoder in addition to assuring accurate data. In general, decoding block code that is relatively easy is commonly employed in dish-shaped storage. In many ECCs, Reed-Solomon codes have the preferred error correction capability, wherein algebraic structure implied in codeword thereof can be implemented in a decoder easily. Because a DVD has a relatively high physical density on the data storage, a DVD system needs an enhanced capability of error correction because more data stored on the DVD is affected in case of damage. In order to obtain a decoder with excellent error correction performance and low complexity, the DVD system typically emploiese Reed-Solomon Product Code (RSPC).
FIG. 1 is a coding block format published by DVD specification. As shown, a data frame is a matrix with a width of 12 bytes and a length of 172 bytes, and an error correction code (ECC) block is a matrix with a width of 208 bytes and a length of 182 bytes, which is formed by superimposing 16 data frames plus corresponding redundancy blocks.
RSPC coding firstly encodes a matrix in column direction. Each byte of a column is regarded as an element of 28 Galois Field (GF) and thus the column can be represented by a polynomial Dcol(x) in GF. The column redundancy is generated based on the following equation:Rcol(x)={Dcol(x)·x16} mod {Gcol(x)},where
            G      col        ⁡          (      x      )        =            ∏              k        =        0            15        ⁢                  ⁢          (              x        +                  α          k                    )      and α is GF primitive element derived by P(x)=x8+x4+x3+x2+1.
Obviously, Rcol(x) is a 16-th order polynomial. Redundancy for each column can be obtained from the coefficients of Rcol(x) and is regarded as 16-byte data. Each column redundancy is also referred to as a column parity. After the aforementioned procedure is applied to each column, the redundancy corresponding to each column is obtained, which is indicated by PO in the coding block of FIG. 1.
After all column parities are generated, redundancy Rrow(x) for each row is subsequently determined. Each byte of a row is regarded as an element of 28 Galois Field (GF) and thus the row can be represented by a polynomial Rrow(x) in GF. The row redundancy is generated based on the following equation:Rrow(x)={Drow(x)·x10}mod{Grow(x)},where
                    G        row            ⁡              (        x        )              =                  ∏                  k          =          0                9            ⁢                          ⁢              (                  x          +                      α            k                          )              ;
Rrow(x) is a 10-th order polynomial. Redundancy for each row can be obtained from the coefficients of Rrow(x) and is regarded as 10-byte data. Each row redundancy is referred to as a row parity. After the aforementioned procedure is applied to each row, the redundancy corresponding to each row is obtained, which is indicated by PI in the coding block of FIG. 1.
Decoding sequence is opposite to the aforementioned coding sequence. Firstly, the row parities are used to decode corresponding rows. Secondly, the column parities are used to decode corresponding columns. Row coding/decoding blocks closer to communication media are referred to as inner codes and their parities are referred to as inner parity (PI) each. By contrast, column coding/decoding blocks are referred to as outer codes and their parities are referred to as outer parity (PO) each.
Erasing addresses can provide more information to a decoder to thus enhance decoding capability. For a DVD system, the encoded codeword is converted by a modulating device from one byte to two bytes, i.e., Eight-to-Sixteen Modulation (ESM). The two bytes are stored in a storage media again. When reading bytes stored in the storage media, a corresponding demodulator is applied. Once the bytes to be read cannot be demodulated properly, it indicates that wrong data is possibly recorded in the corresponding address. In this case, the byte's address is set as an erasing address so that the decoder only needs to compute the address's deviation for error correction while the byte is wrong. Theoretically, the decoder knowing the erasing address can have error correction capability twice than that not knowing the erasing address.
As aforementioned, Reed-Solomon Product Code (RSPC) employed by DVD systems generates parities for columns and rows of a 2D matrix. On decoding, an iterative method is frequently used to increase error correction capability. FIG. 2 is a decoding flowchart using a typical iterative method. As shown in FIG. 2, firstly, row decoding is performed. When a row is properly decoded, all erasing addresses of the row are eliminated; otherwise the erasing addresses of the row are remained to be corrected by next column decoding. Secondly, column decoding is performed. When a column is properly decoded, all erasing addresses of the column are eliminated; otherwise the erasing addresses of the column still are remained to be corrected by next row decoding. The aforementioned procedure is repeated until parity check is all right; i.e., decoding is successful. If iteration is met but error correction is not complete, it means that the decoding is failed. Such a decoding is proportional to memory access number, repeat number of decoding iteration, and power consumption; i.e., higher iteration number will consume more power. Therefore, it is desirable to provide an improved device and method to mitigate and/or obviate the aforementioned problems.